/*************************************************************************
    > File Name: RSA.cpp
    > Author: ZhaoLulu@BJTU
    > E-mail: 19281121@bjtu.edu.cn
    > Created Time: 2021年11月16日 星期二
 ************************************************************************/
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include "RSA.h"

using namespace std;

int exp_euclid(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exp_euclid(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}

int modular_exponent(int a, int b, int n) {
    int f = 1;
    vector<int> bb;
    while (b != 0) {
        bb.push_back(b % 2);
        b /= 2;
    }
    for (int i = (int) bb.size(); i > 0; i--) {
        f = (f * f) % n;
        int x = bb.at(i - 1);
        if (x == 1) {
            f = (f * a) % n;
        }
    }
    return f;
}

int euler(int n) {
    int res = n;

    int j = 2;
    set<int> prim_set;
    while (j * j <= n) {
        if (n % j == 0) {
            prim_set.insert(j);
            n /= j;
        } else {
            j++;
        }
    }
    prim_set.insert(n);

    auto iter = prim_set.begin();
    while (iter != prim_set.end()) {
        res = res / (*iter) * ((*iter) - 1);
        iter++;
    }
    return res;
}

int main() {
    cout << "----------------扩展欧几里得算法求解乘法逆元测试----------------" << endl;
    int x, y;
    int a = 3, b = 8;
    int d = exp_euclid(a, b, x, y);
    cout << "gcd(a,b) = " << "gcd(" << a << "," << b << ") = " << d << endl;
    cout << a << " * " << x << " + " << b << " * " << y << " = gcd(a,b) = " << d << endl;
    cout << "------------------------------------------------------------" << endl;

    cout << "-----------------------快速模幂算法测试-----------------------" << endl;
    int aa = 7, bb = 560, n = 561;
    cout << aa << "^" << bb  << " mod " << n << " = " << modular_exponent(aa, bb, n) << endl;
    cout << "------------------------------------------------------------" << endl;

    cout << "---------------------欧拉函数值求解算法测试--------------------" << endl;
    ofstream out;
    out.open("euler.txt");
    for (int i = 100; i <= 1000; ++i) {
        out << i << ":\t" << euler(i) << endl;
    }
    cout << "这里给出前20个为例，完整数据在/cmake-build-debug/euler.txt中" << endl;
    for (int i = 100; i <= 119; ++i) {
        cout << i << ":\t" << euler(i) << endl;
    }
    cout << "------------------------------------------------------------" << endl;

    return 0;
}
